A conventional packet scheduling method under a wireless communication environment is provided for a CDMA-1x-EVDO (HDR). The conventional packet scheduling method for a data service under a CDMA environment is designed for maximizing throughput of a wireless communication system with enlarging amount of data in response to characteristics of the wireless environment.
It is well known by the people skilled in the art that, as the conventional packet scheduling method, there are a Proportional Fair (PF) method, a Modified-Largest Weighted Delay First (M-LWDF) method, and a proportional delay scheduling method.
Design objective of the PF algorithm is to maximize long-term throughput of a user equipment (UE) whose current channel status, i.e., achievable data rate is better as compared with an average throughput. It is assumed that Rk(t) and Tk(t) are the current achievable data rate and the estimate of average throughput of a user k at a timeslot t. Then, in the PF algorithm, an average throughput Tk(t) can be determined as a following equation 1.
                                          T            k                    ⁡                      (                          t              +              1                        )                          =                  {                                                                                                                                        (                                                  1                          -                                                      1                            /                                                          t                              c                                                                                                      )                                            ⁢                                                                        T                          k                                                ⁡                                                  (                          t                          )                                                                                      +                                                                  1                        /                                                  t                          c                                                                    ⁢                                                                        R                          k                                                ⁡                                                  (                          t                          )                                                                                                      ,                                                                              k                  =                                      k                    *                                                                                                                                                                  (                                              1                        -                                                  1                          /                                                      t                            c                                                                                              )                                        ⁢                                                                  T                        k                                            ⁡                                              (                        t                        )                                                                              ,                                                                              k                  ≠                                      k                    *                                                                                                          [                  Equation          ⁢                                          ⁢          1                ]            
Where, k is one of a present user set, i.e., plural users; k* is a predetermined user receiving a data during a previous timeslot; and tc is a parameter of a low pass filtering for obtaining the moving average of throughput Tk(t). Generally, 1000 timeslots is recommended as tc.
As following equation 2, a predetermined user with the highest ratio ofRk(t)/Tk(t)among the plural users will receive transmission from a base station (BS) at each scheduling time. Herein, with a reference, ties are broken randomly.
                              k          *                =                  arg          ⁢                                          ⁢                                    max              k                        ⁢                                                  ⁢                                                            R                  k                                ⁡                                  (                  t                  )                                                                              T                  k                                ⁡                                  (                  t                  )                                                                                        [                  Equation          ⁢                                          ⁢          2                ]            
However, since the PF algorithm is designed to support only data services in CDMA-1x-EVDO system, it can not support real-time services such as a voice service and a real-time video streaming service.
Further, the PF algorithm is not suitable for a relatively short-time service because of a low pass filtering used for calculating the moving average of throughput Tk(t).
Meanwhile, the M-LWDF algorithm was proposed to support not only non-real-time data services but also almost real-time services such as video streaming services in CDMA-1x-EVDO (HDR) system. Design objective is to maintain delay of each traffic smaller than a predefined threshold value with probability.
Delay and throughput requirements of the M-LWDF algorithm are described as the following equation 3.Pr{Wk>τk}≦δk Tk<tk  [Equation 3]
Where, Wk is a Head of Line (HoL) delay value; τk is a maximum allowable threshold of the HOL delay; δk is a maximum allowable probability of exceeding tk; Tk is a minimum required throughput; and tk is a throughput.
Therefore, by a packet scheduling algorithm based on the above described requirements, in each time-slot t, a user k* is selected according to the scheduling priority as the following equations.
                                                                        k                *                            =                            ⁢                              arg                ⁢                                                      max                    k                                    ⁢                                                            γ                      k                                        ⁢                                                                  W                        k                                            ⁡                                              (                        t                        )                                                              ⁢                                                                  D                        k                                            ⁡                                              (                        t                        )                                                                                                                                                                                    γ                k                            =                            ⁢                                                a                  k                                ⁢                                                      T                    k                                    ⁡                                      (                    t                    )                                                                                                                                          a                k                            =                            ⁢                                                -                                      (                                          log                      ⁢                                                                                          ⁢                                              δ                        k                                                              )                                                  ⁢                                  τ                  k                                                                                        [                  Equation          ⁢                                          ⁢          4                ]            
Where, Dk(t) is an average channel rate with respect to flow k; Wk(t) is a HOL delay of the k; and γk is a predetermined positive value.
The M-LWDF algorithm can provide a preferred service by setting an appropriate value of each parameter γk for each k to thereby satisfy the above delay requirements. Herein, the γk plays an important role for determining a scheduling priority. However, it is practically difficult to find an optimal value of γk for each traffic; and, as a result, γk intuitively determined cannot be preferable for the wireless communication system.
Lastly, the proportional delay scheduling used for transmitting a packet data is described hereinafter.
A Priority Function (PF) used for the proportional delay scheduling is calculated by a user packet delay time. The PF of a user is adjusted when a delay value of the user is in excess of the delay threshold.
For example, a delay function used in PF calculation is calculated by a first average data rate required to all users in activated set having uncertain data and a second average data rate previously arranged to each user.
For increasing a delay sensitiveness, the algorithm for use in the proportional delay scheduling method adjusts the PF and provides an appropriate delay request and a consistent scheduling; and, as a result, the algorithm can support a exceptional or predetermined delay request from each user.
It is assumed that there is a delay requirement time of users “d” and each base station allocates a delay threshold delay τi to each user.
If a data rate of each user is called as “DRC” and throughput is called as “T” a proportional pair (or priority function) is derived as DRC/T or (DRC/T)g(d). Herein, said g(d) means a threshold function of a user d.
Further, a threshold function of a predetermined user di can be defined as the equation g(di)=1+k*(max(0,(di−τi)). Therefore, a scheduling priority function is derived as the equation PFi=(DRCi/Ti)g(di). The above described scheduling method can perform variable delay functions, each corresponding to a requirement, a capability, and a range of communication system. However, it can not support a packet scheduling according to a channel state.
The conventional scheduling methods handle a packet scheduling in CDMA-EVDO (HDR); focus on effective packet scheduling about a non-real-time traffic service rather than a real-time service such as a voice and a streaming. Thus, there is a problem that the conventional scheduling methods are inappropriate under a mixed traffic environment including a real-time traffic and a non-real-time traffic.
In a mobile communication system based on a packet traffic except for a Universal Mobile Telecommunication System (UMTS), as one of 3rd generation system based on W-CDMA, which provides a scheduling about an interactive service, a background service, and a streaming service but a voice service, there is needed an algorithm for supporting a data scheduling in response to characteristics of a real-time traffic and a non-real-time traffic since the real-time traffic and the non-real-time traffic should be scheduled. With reference, in UMTS, the voice service is provided through a separate channel, i.e., the voice service and other services such as the interactive service, the background service, and the streaming service are not commonly provided through the same channel.
In addition, there is required a packet scheduling method for transmitting each packet to each of plural users per every timeslot (TS), not transmitting packets to only one user selected per every timeslot (TS) like a CDMA-EVDO. Also, it is required that a packet scheduling method can be adaptive and effective for providing a packet transmission in response to an amount of traffics and a construction of traffics varied according to time.
That is, for improving a communication service quality, there is required a packet scheduling method which is for supporting a scheduling in response to a characteristic of a real-time traffic and a delay sensitively; providing a scheduling based on a channel state and a delay requirement, which relate to a throughput, for effectively transmitting a non-real-time traffic affected by the throughput; and for adaptively and effectively improving a service quality considering to amount of traffic and a construction change of transmitted packets according to the time.